# 统计一个数字在排序数组中出现的次数。
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
# 输入: nums = [5,7,7,8,8,10], target = 8
# 输出: 2


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        l = self.binary_search_lt(nums, target)
        r = self.binary_search_gt(nums, target)
        return 0 if r - l == 1 else r - l - 1

    # 查找第一个比target小的数
    def binary_search_lt(self, nums: list, target: int):
        l, r = -1, len(nums)
        while l + 1 != r:
            mid = (l + r) // 2
            if nums[mid] < target:
                l = mid
            else:
                r = mid
        return l

    # 查找第一个比target大的数
    def binary_search_gt(self, nums: list, target: int):
        l, r = -1, len(nums)
        while l + 1 != r:
            mid = (l + r) // 2
            if nums[mid] <= target:
                l = mid
            else:
                r = mid
        return r

class Solution1:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A
